/**
 * 队列完 + 二叉树
 *
 */
public class Test {
    /**
     * 二叉树
     * @param args
     *      1.树型结构
     *      2.二叉树
     *
     */
    /**
     * 二叉树
     * @param args
     *      1.二叉树的概念
     *      2.特殊的两种二叉树
     *      3.二叉树的性质
     *      4.二叉树的存储
     *      5.二叉树的基本操作
     */
    /**
     * 二叉树的基本操作
     *      1.前置说明(创建二叉树)->BinaryTree演示
     *      2.二叉树的遍历->BinaryTree演示
     */
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        BinaryTree.TreeNode ret = binaryTree.createBinaryTree();
        System.out.println(ret.val);

        binaryTree.preOrder(ret);
        System.out.println();
        binaryTree.inOrder(ret);
        System.out.println();
        binaryTree.postOrder(ret);
        System.out.println();
    }
    public static void main9(String[] args) {
        /**
         * 二叉树的存储:顺序存储 和类似于链表的链式存储
         * 类似于链表的链式存储:通过一个一个节点引用起来的
         * 一般节点使用二叉树(孩子表示法)/三叉树(孩子双亲表示法)
         */
    }
    public static void main8(String[] args) {
        /**
         * 二叉树的性质:
         *      1.若规定根节点层次为1,则一颗非空二叉树第i层节点个数最多为2^(k - 1)
         *      2.若规定根节点的深度为1,则一颗非空二叉树所有节点个数最多为2^K - 1
         *      3.对于任意二叉树,叶子节点个数为n0,度为2的节点为n2,则有 n0 = n2 + 1,(推算,N个节点有N-1条边,N-1 = n1 + 2*n2,则有no + n1 + n2 = n1 + 2*n2 + 1)
         *      4.对于完全二叉树,节点个数为N,求高度为log2(N + 1)向上取整
         *      5.对应具有n个节点的完全二叉树,从根节点开始从左向右,以0开始编号
         *      当子节点为i>0时,双亲结点编号为(i + 1) / 2,i = 0,为根节点
         *      当2i + 1 < N,左节点编号为2i + 1,如果大于,则无左孩子
         *      当2i + 2 < N,右节点编号为2i + 2,如果大于,则无右孩子
         */
    }
    public static void main7(String[] args) {
        /**
         * 特殊的两种二叉树:满二叉树 完全二叉树
         * 满二叉树:每个层次的结点个数都达到最大值(即每层有2^(k - 1)个节点,所有节点个数为(2^k) - 1)
         * 完全二叉树:二叉树节点从上到下从左到右依次存放,不能空缺.
         * 满二叉树是特殊的完全二叉树.
         */
    }
    public static void main6(String[] args) {
        /**
         * 概念:一颗二叉树是节点的有限结合,该集合:
         *      1.或者为空
         *      2.或者是由一个根节点加上两颗分别称为左子树和右子树二叉树组成
         * 注意:
         *      1.子树只能<=2
         *      2.有左右之分,不能颠倒
         */
    }
    /**
     * 树型结构
     * @param args
     *      1.树的概念(基础)
     *      2.树的概念(重要)
     *      3.树的表示形式
     *      4.树的应用
     */
    public static void main5(String[] args) {
        /**
         * 树的应用:文件系统管理
         */
    }
    public static void main4(String[] args) {
        /**
         * 树的表示形式:双亲表示法 孩子表示法 孩子双亲表示法 孩子兄弟表示法(常用)
         * 使用内部类抽象出:数值域 孩子引用 兄弟引用
         */
    }
    public static void main3(String[] args) {
        /**
         * 树的概念(重要)
         *  1.节点的度:一个节点拥有子节点的个数
         *  2.树的度:树所有节点的度的最大值
         *  3.叶子节点/终端节点:没有子节点的结点
         *  4.双亲结点/父亲节点:如果一个节点拥有子节点,则称为该节点是子节点的双亲节点/父亲节点
         *  5.孩子节点/子节点:一个节点含有子树的根节点则称为该节点的子节点
         *  6.根节点:没有双亲结点的节点
         *  7.节点的层次/深度:从根节点开始为1,根节点的子节点为2,依次类推
         *  8.树的高度:树的最大层次/深度.
         *  9.非终端节点/分支节点:度不为0的结点
         *  10.兄弟节点:父节点相同的子节点
         *  11.堂兄弟节点:父节点在同一层次的子结点
         *  12.节点的祖先:从根到该节点所经分支的所有节点
         *  13.子孙:以某节点为根的子树中,任一节点都称为该节点的子孙
         *  14.森林:由m颗互不相交的树组成的集合
         */
    }
    public static void main2(String[] args) {
        /**
         * 树的概念:一种非线性的数据结构,由n个有限结点组成一个具有层次关系的集合.
         * 叫做树原因,像一颗倒挂的树,根节点在上,叶子节点朝下
         * 特点:1.特殊的结点称为根节点,没有前驱结点(即除根节点外,其它节点仅有一个父亲节点)
         * 2.除根节点以外,其它叶子节点被分为M个子树,每个根节点有且仅有一个前驱节点,有0个或多个后继节点
         * 3.树是递归定义的
         * 4.子树不相交
         * 5.一颗N个节点的树,由N-1条边
         */
    }
    /**
     * 栈实现队列
     * @param args
     */
    public static void main1(String[] args) {
        MyQueue myQueue = new MyQueue();
        myQueue.push(1);
        myQueue.push(2);
        System.out.println(myQueue.peek()); // return 1
        System.out.println(myQueue.pop()); // return 1, queue is [2]
        System.out.println(myQueue.empty()); // return false
    }
}
